
/**
 * 分披萨
 * 
 * 题目描述

"吃货"和"馋嘴"两人到披萨店点了一份铁盘（圆形）披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。

由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：从"吃货"开始，轮流取披萨。除了第一块披萨可以任意选取外，其他都必须从缺口开始选。

他俩选披萨的思路不同。"馋嘴"每次都会选最大块的披萨，而且"吃货"知道"馋嘴"的想法。

已知披萨小块的数量以及每块的大小，求"吃货"能分得的最大的披萨大小的总和。


输入描述
第 1 行为一个正整数奇数 N，表示披萨小块数量。

3 ≤ N < 500
接下来的第 2 行到第 N + 1 行（共 N 行），每行为一个正整数，表示第 i 块披萨的大小

1 ≤ i ≤ N
披萨小块从某一块开始，按照一个方向次序顺序编号为 1 ~ N

每块披萨的大小范围为 [1, 2147483647]

输出描述
"吃货"能分得到的最大的披萨大小的总和。
 */

 /**
  * 
用例
输入	5
8
2
10
5
7
输出	19
说明	
此例子中，有 5 块披萨。每块大小依次为 8、2、10、5、7。
按照如下顺序拿披萨，可以使"吃货"拿到最多披萨：
"吃货" 拿大小为 10 的披萨
"馋嘴" 拿大小为 5 的披萨
"吃货" 拿大小为 7 的披萨
"馋嘴" 拿大小为 8 的披萨
"吃货" 拿大小为 2 的披萨
至此，披萨瓜分完毕，"吃货"拿到的披萨总大小为 10 + 7 + 2 = 19
可能存在多种拿法，以上只是其中一种。

  */

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 
 * 解析
 * 利用递归来求解
 * 第一轮，"吃货"可以拿任意一块披萨。而"吃货"拿完后，披萨铁盘就会产生缺口，而"馋嘴"取走披萨是明确的，就是缺口左右两边中较大者。
 * 第二轮，"吃货"需要从披萨铁盘的缺口处选择，有两种：

选择缺口左边的披萨
选择缺口右边的披萨
此时我们可以进行递归开两个分支，分别去尝试此轮取左边，和此轮取右边，最终选取两种方式中可以给"吃货"带来最大披萨大小的那个值。

而一旦"吃货"选完，"馋嘴"选取的披萨是明确的，即缺口左右两边中较大值。

可以加入缓存优化，即将某个缺口状态下，"吃货"能获得的最大披萨大小记录下来

递归的缓存优化策略

 * 
 * 
 */

public class 分披萨 {

    //记录吃货的获取最大披萨的大小
    private static long pizzaTotalSize = 0;
    //披萨大小数组
    private static long[] pizzaSize;

    public static void main(String[] args){

        try{

            Scanner scanner = new Scanner(System.in);
            //获取披萨块数
            int pizzaCount = scanner.nextInt();
            //披萨大小数组
            pizzaSize = new long[pizzaCount];

            for(int i=0; i<pizzaCount; i++){

                pizzaSize[i] = scanner.nextInt();
            }

            //无缓存递归，递归会超时
            //noCache();

            //缓存递归，不会超时
            withCache();

        }catch(Exception e){
            e.printStackTrace();
            //System.out.println("程序异常"+(null==e ? "" : e.getMessage()));
        }
    }

    private static long[][] pizzaCache;

    private static void withCache(){
        pizzaCache = new long[pizzaSize.length][pizzaSize.length];

        //循环遍历
        for(int i=0; i<pizzaSize.length; i++){

            // i - 1 是缺口的左边披萨，check函数作用是防止 i - 1 越界, 进行绕环运动
            // i + 1 是缺口的右边披萨，check函数作用是防止 i + 1 越界，进行绕环运动
            // recursive的作用求解是"吃货"从缺失了 第 i 块的披萨铁盘 开始选，最终可得的最大披萨大小，
            // 而第 i 块是首轮就被"吃货"拿走的，因此是takeBigger + pizza[i]

            System.out.println("循环下标="+i);

            pizzaTotalSize = Math.max(pizzaTotalSize,
             takeBiggerWithCache(checkIndex(i-1), checkIndex(i+1))+pizzaSize[i]);
        }

        System.out.println(pizzaTotalSize);



    }

    private static long takeBiggerWithCache(int left, int right){

        System.out.println("递归下标-left="+left+"right="+right);

         // 进入递归前，"吃货"已经拿了披萨，因此进入递归后，轮到"馋嘴"拿
        // 而"馋嘴"拿披萨的策略固定是：缺口左右两边中较大的那块
        if(pizzaSize[left] > pizzaSize[right]){

            // 拿走第 l 块，因此缺口左边的位置变为 l - 1
            left = checkIndex(left - 1);
            System.out.println("馋嘴取 left="+left);
        } else{

            // 拿走第 r 块，因此缺口右边的位置变为 r + 1
            right = checkIndex(right + 1);
            System.out.println("馋嘴取 right="+right);
        }

        //缓存中是否已经有该 key 的 值  key = "pizza_"+left+"_"+right
        if(pizzaCache[left][right] > 0){

            System.out.println("命中缓存");

            return pizzaCache[left][right];
        }

        if(left == right){

            //递归结束
            // 当 l == r 是，说明只剩一块披萨了，由于奇数个披萨，且"吃货"第一个拿，因此最后一个也是"吃货"拿
            System.out.println("left == right="+left);
            pizzaCache[left][right] = pizzaSize[left];
        } else {

            // 如果还剩多块披萨，那么"吃货"有两种选择：
            // 1、拿缺口左边的披萨
            // 2、拿缺口右边的披萨
            // 因此这里直接开两个递归分支，最终结果取较大值
            System.out.println("开始递归 == left="+checkIndex(left-1)+"right="+checkIndex(right+1));

            pizzaCache[left][right] = Math.max(takeBiggerWithCache(checkIndex(left-1), right)+pizzaSize[left], 
            takeBiggerWithCache(left, checkIndex(right+1))+pizzaSize[right]);

        }

        return pizzaCache[left][right];
    }

    private static void noCache(){

        //循环遍历
        for(int i=0; i<pizzaSize.length; i++){

            // i - 1 是缺口的左边披萨，check函数作用是防止 i - 1 越界, 进行绕环运动
            // i + 1 是缺口的右边披萨，check函数作用是防止 i + 1 越界，进行绕环运动
            // recursive的作用求解是"吃货"从缺失了 第 i 块的披萨铁盘 开始选，最终可得的最大披萨大小，
            // 而第 i 块是首轮就被"吃货"拿走的，因此是takeBigger + pizza[i]

            System.out.println("循环下标="+i);

            pizzaTotalSize = Math.max(pizzaTotalSize,
             takeBigger(checkIndex(i-1), checkIndex(i+1))+pizzaSize[i]);
        }

        System.out.println(pizzaTotalSize);

    }

    //递归  分治，同时计算左边拿和右边拿并得到最大的那个披萨，如果只剩下最后一块，则直接给吃货，因为最后一块必然是吃货拿到
    public static long takeBigger(int left, int right){

        System.out.println("递归下标-left="+left+"right="+right);

         // 进入递归前，"吃货"已经拿了披萨，因此进入递归后，轮到"馋嘴"拿
        // 而"馋嘴"拿披萨的策略固定是：缺口左右两边中较大的那块
        if(pizzaSize[left] > pizzaSize[right]){

            // 拿走第 l 块，因此缺口左边的位置变为 l - 1
            left = checkIndex(left - 1);
            System.out.println("馋嘴取 left="+left);
        } else{

            // 拿走第 r 块，因此缺口右边的位置变为 r + 1
            right = checkIndex(right + 1);
            System.out.println("馋嘴取 right="+right);
        }

        if(left == right){

            //递归结束
            // 当 l == r 是，说明只剩一块披萨了，由于奇数个披萨，且"吃货"第一个拿，因此最后一个也是"吃货"拿
            System.out.println("left == right="+left);
            return pizzaSize[left];
        } else {

            // 如果还剩多块披萨，那么"吃货"有两种选择：
            // 1、拿缺口左边的披萨
            // 2、拿缺口右边的披萨
            // 因此这里直接开两个递归分支，最终结果取较大值
            System.out.println("开始递归 == left="+checkIndex(left-1)+"right="+checkIndex(right+1));
            return Math.max(takeBigger(checkIndex(left-1), right)+pizzaSize[left], 
            takeBigger(left, checkIndex(right+1))+pizzaSize[right]);

        }

    }

    //防止下标越界
    private static int checkIndex(int index){

        if(index < 0){

            return pizzaSize.length - 1;

        } else if(index >= pizzaSize.length){

            return 0;
        }

        return index;
    }

    
}
